package interview.huawei.tjt.training.huisu;

import java.util.*;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
 *
 * 示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [   [2,2,2,2],   [2,3,3],   [3,5] ]
 */
public class ZuHeZongHe1 {

    private static List<List<Integer>> result = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String[] str = sc.nextLine().split(",");
            int[] candidates = new int[str.length];
            for (int i = 0; i < str.length; i ++) {
                if (!str[i].equals("") && str[i] != null) {
                    candidates[i] = Integer.parseInt(String.valueOf(str[i]));
                }
            }
            Arrays.sort(candidates);
            // k为target的值
            int k = sc.nextInt();
            helper(candidates, k, 0, 0);
            System.out.println(result);
            // 清理上一次的输出结果
            result.clear();
        }

    }

    public static void helper (int[] candidates, int k,int sum,int id) {

        // 终止条件
        if (sum == k) {
            Collections.sort(path);
            // 去除重复元素
            if (result.contains(new ArrayList<>(path))) {
                return;
            }
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = id; i < candidates.length; i ++) {
            if (sum + candidates[i] > k) {
                break;
            }
            path.add(candidates[i]);
            helper(candidates, k, sum + candidates[i], i);
            // 回溯
            path.remove(path.size() - 1);
        }
    }

}
